Data transmission 10 (FIG. 1) involves a transfer of information known as data between a sender 12 and a receiver 14. Often, data transmission 10 includes information transmitted as digital bits of ones and zeros, represented here by mn−1 to m0, and referred to as a message M.
In a perfect world, message M transmits free of errors. Unfortunately, errors are often introduced though medium 16 by which message M travels from sender 12 to receiver 14 (e.g., medium 16 may be any combination of wire, cable, fiber-optic, air, or link layer devices). One method for detecting the presence of errors in message M employs cyclic redundancy codes.
Cyclic redundancy codes treat groupings of digital bits like message M as a polynomial where each bit in the grouping represents a coefficient in the polynomial Xn−1+Xn−2+X0. For example, a group of eight bits 11001101 may be represented by polynomial X7+X6+X3+X2+1 (i.e., 1*X7+1*X6+0*X5+0*X4+1*X3+1*X2+0*X1+1*X0).
These polynomials form an algebraic object known as a commutative ring with coefficients in Z/p where Z are the integers and p is a prime number, here 2, also known as {0,1} modulo 2. A non empty set R together with two binary operations {+*} is called a ring if (R+) is an abelian group, (R*) is a semi group and the distributive laws are obeyed, (i.e. a*(b+c)=a*b+a*b).
In polynomial rings, there are no carries or borrows from one coefficient to the next. In arithmetic modulo 2, addition and subtraction are identical and may be implemented with exclusive-or.
            10111011              10110011              11110000              00010101                                                +            11001110                    ⁢                                                _                                                  +            11000101                    ⁢                                                _                                                  -            00100110                    ⁢                                                _                                                  -            10101111                    _                ⁢                                                  01110101              01110110              11010110              10111010      
Division of polynomials represented as groups of bits is completed in a manner similar to binary division except subtraction is done in modulo2. A divisor will ‘go into’ a dividend if the dividend polynomial is of the same degree as the divisor polynomial (i.e., the divisor and dividend share at least the same most significant bit).
A cyclic redundancy code may be obtained by calculating the remainder for message M divided by a generator polynomial P. This remainder is called a cyclic redundancy code (“CRC”).
To obtain a CRC for a message M, the group of bits to be divided by generator polynomial P may include appended zero-bits 17. Zero-bits 17 are equal in number to the degree of generator polynomial P. Thus, the CRC of a message M=10111000 having three appended zero-bits 17 based on a generator polynomial P=X3+1=1001 of degree three (i.e., where X3 is the most significant bit of polynomial P) may be calculated as follows:

The resulting remainder, shown as CRC 18, may be appended to message M, replacing zero bits 17, to create a message M′. Sender 12 transmits message M′ via medium 16 to receiver 14 as data transmission 10.
Upon receipt, receiver 14 divides message M′ by the same generator polynomial P to obtain a CRC for M′ and check the validity of data transmission 10. If the resulting remainder is zero (i.e., CRC=M′(modulo)P=0), the integrity of data transmission 10 is confirmed. For example:

If the remainder of message M′ divided by polynomial P is not zero (i.e., CRC=M′(modulo)P≠0), data transmission 10 contains one or more errors. For example:

Like reference symbols in the various drawings indicate like elements.